﻿// 5843. 染色.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/5846/

给定一棵 n
 个节点的树，节点编号为 1∼n
。

每个节点都被染成了黑色（用 1
 表示）或白色（用 0
 表示）。

从黑色节点无法到达白色节点，反之亦然。

因此，两个同色节点相互可达的前提是，两个同色节点之间的路径中不含另一种颜色的节点。

我们希望将树中的所有节点都染成同一种颜色（全黑或全白均可）。

为此，你可以采用我们指定的染色操作。

每次操作可以选择一个节点 v
，并改变节点 v
 以及其所有可达同色节点的颜色（黑变白、白变黑）。

例如，在下图中，点 1
 和点 2,3,8,9
 之间相互可达，但是点 1
 和点 6
 之间相互不可达（被点 5
 挡住了），因此，如果选择点 1
 进行染色操作，会将点 1,2,3,8,9
 全部染黑。

a.png

请你计算，为了达成目标，至少需要进行多少次染色操作。

输入格式
第一行包含整数 n
。

第二行包含 n
 个整数 c1,c2,…,cn
，其中 ci
 为节点 i
 的颜色（1
 表示黑，0
 表示白）。

接下来 n−1
 行，每行包含两个整数 ui,vi
，表示节点 ui
 和节点 vi
 之间存在一条边。

输出格式
一个整数，表示所需的最少染色操作次数。

数据范围
前 3
 个测试点满足 1≤n≤15
。
所有测试点满足 1≤n≤2×105
，0≤ci≤1
，1≤ui,vi≤n
，ui≠vi
。

输入样例1：
11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11
输出样例1：
2
输入样例2：
4
0 0 0 0
1 2
2 3
3 4
输出样例2：
0
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 